/**
 *给你一个二维整数数组intervals，其中intervals[i] = [lefti, righti]表示 闭区间[lefti, righti]。
 *
 * 你需要将intervals 划分为一个或者多个区间组，每个区间 只属于一个组，且同一个组中任意两个区间 不相交。
 *
 * 请你返回 最少需要划分成多少个组。
 *
 * 如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交的。比方说区间[1, 5] 和[5, 8]相交。
 *
 *
 *
 * 链接：https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups
 */
class MinGroups {
    public int minGroups(int[][] intervals) {
       int max=intervals[0][1];
        for(int[] interval:intervals) {
            max=Math.max(max,interval[1]);
        }
        int[] diff=new int[max+2];//构造差分数组，因为一开始没有区间，所以初始值都是0，后面如果遇到一个区间，就将区间内所有值加1，这样到最后公共区域重叠最多的就有多少组
        for(int[] interval:intervals) {//在区间[interval[0],interval[1]]内的所有值加1，也就是将diff[interval[0]]加1，和将diff[interval[1]+1]加1，这样就算将区间[interval[0],interval[1]]内的所有值加1了（原理看差分数组）
            diff[interval[0]]+=1;
           
                diff[interval[1]+1]-=1;
          
        }
        int t=0,ans=0;
        for(int i=1;i<=max;i++) {//将差分数组还原，重叠最高的，就有多少组，差分数组构建是 ：差分[i]=nums[i]-nums[i-1];所以在还原是nums[i]=nums[i-1]+差分[i],只是这里用t代替差分[i]
            t=t+diff[i];
            ans=Math.max(ans,t);
        }
        return ans;
    }
}